#include <SFML/Window.hpp>
#include <SFML/Graphics.hpp>
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <algorithm>
#include <unordered_map>
#include <chrono>
#include "vec2.cpp"
#include "room.cpp"

#define DELTA (0.00001)
#define PI (3.14159265358979)
/*
std::vector<std::vector<vec2>> slice_polygon(std::vector<vec2> polygon, vec2 org, vec2 v) {
    int faces[2];
    vec2 points[2];
    int k = 0;
    for(int i = 0; i < polygon.size(); i ++) {
        vec2 prev = polygon[i - 1 + polygon.size() * (!i)];
        vec2 next = polygon[i];
        double t = get_intersection(prev, next - prev, org, v);
        vec2 point = prev * (1 - t) + next * t;
        if(0 <= t && t <= 1 && std::find(points, points + 2, point) == points + 2) {
            faces[k] = i;
            points[k] = point;
            k ++;
            if(k == 2) break;
        }
    }
    if(k != 2) return std::vector<std::vector<vec2>>(1, polygon);
    std::vector<vec2> poly1;
    poly1.push_back(points[0]); poly1.push_back(points[1]);
    for(int i = faces[1]; i < polygon.size(); i ++)
        if(std::find(poly1.begin(), poly1.end(), polygon[i]) == poly1.end()) poly1.push_back(polygon[i]);
    for(int i = 0; i < faces[0]; i ++)
        if(std::find(poly1.begin(), poly1.end(), polygon[i]) == poly1.end()) poly1.push_back(polygon[i]);
    std::vector<vec2> poly2;
    poly2.push_back(points[1]); poly2.push_back(points[0]);
    for(int i = faces[0]; i < faces[1]; i ++)
        if(std::find(poly2.begin(), poly2.end(), polygon[i]) == poly2.end()) poly2.push_back(polygon[i]);
    std::vector<std::vector<vec2>> polygons;
    if(poly1.size() > 2) polygons.push_back(poly1);
    if(poly2.size() > 2) polygons.push_back(poly2);
    return polygons;
}
*/
double area(std::vector<vec2> polygon) {
    double a = 0;
    for(int i = 0; i < polygon.size(); i ++) {
        vec2 prev = polygon[i - 1 + polygon.size() * (!i)];
        vec2 next = polygon[i];
        a += (prev.x - next.x) * (prev.y + next.y);
    }
    return a / 2;
}

struct Room_info {
    int rotaion;
    Room * room;
    vec2 origin;
    std::vector<vec2> polygon;
};

class Backrooms {
    public:
    std::unordered_map<int, Room> rooms;
    Room * origin_room;
    int origin_rotation = 0;
    vec2 origin_pos = vec2(.5, .5);
    double angle = 0.;
    int room_size;
    vec2i image_size = vec2(1080, 720);
    sf::RectangleShape human;
    std::list<sf::RectangleShape> poops;
    std::list<sf::CircleShape> marks;

    Backrooms(sf::RectangleShape human, int room_size) : human(human), room_size(room_size) {
        origin_room = &add_room(sf::Color(140, 90, 90));
    }
    
    void add_random(int n) {
        while(rooms.size() < n) add_room(sf::Color(100 + rand() % 30, 100 + rand() % 30, 100 + rand() % 30));
        for(;;) {
            std::pair<std::vector<int>, std::vector<int>> c = connectivity();
            if(!c.second.size()) break;
            for(int i : c.second)
                connect(rooms[c.first[rand() % c.first.size()]], rand() % 4, rooms[i], rand() % 4);
        }
        /*for (int i = 0; i < n / 3; i++) {
            Room & r1 = std::next(rooms.begin(), rand() % rooms.size())->second;
            int d1 = rand() % 4;
            Room & r2 = std::next(rooms.begin(), rand() % rooms.size())->second;
            int d2 = rand() % 4;
            if(r1.connected_rooms[d1] < 0 && r2.connected_rooms[d2] < 0)
                connect(r1, d1, r2, d2);
        }*/
    }

    std::pair<std::vector<int>, std::vector<int>> connectivity() {
        std::vector<int> unconnected;
        std::vector<int> connected(1, origin_room->id);
        for(std::pair<const int, Room> & r : rooms) {
            if(r.first != origin_room->id)
                unconnected.push_back(r.first);
        }
        bool found;
        do {
            found = false;
            for(int i : connected) {
                for(int j : rooms[i].connected_rooms) {
                    std::vector<int>::iterator k = std::find(unconnected.begin(), unconnected.end(), j);
                    if(k != unconnected.end()) {
                        connected.push_back(j);
                        unconnected.erase(k);
                        found = true;
                        break;
                    }
                }
                if(found) break;
            }
        } while(found);
        return std::pair<std::vector<int>, std::vector<int>>{connected, unconnected};
    }
    
    std::pair<int, Room*> get_room(vec2 point) {
        double dist = 0.;
        vec2 p = origin_pos;
        vec2 v = norm(point - origin_pos);
        int rotation = origin_rotation;
        Room * room = origin_room;
        vec2i cell(0, 0);
        int m = 0;
        while(abs(point - origin_pos) > dist) {
            vec2i next_cell = f2i(p) - (v < 0) * vec2(p.x == f2i(p.x), p.y == f2i(p.y));
            if(cell != next_cell) {
                int dir;
                if(cell.x != next_cell.x) dir = next_cell.x > cell.x ? 1 : 3;
                else dir = next_cell.y > cell.y ? 2 : 0;
                dir = (dir + 4 - rotation) % 4;
                rotation = (rotation + dir + 6 - room->backwards_doors[dir]) % 4;
                room = &rooms[room->connected_rooms[dir]];
                cell = next_cell;
            }
            vec2 walls = cell + (v > 0);
            vec2 t = (walls - p) / v;
            p += v * t.min();
            dist += t.min();
            if(t.x < t.y) p.x = walls.x;
            else p.y = walls.y;
            m ++;
        }
        return std::pair<int, Room*>{rotation, room};
    }

    std::pair<vec2i, std::vector<vec2>> extrude(vec2 p1, vec2 p2) {
        vec2 midp = (p1 + p2) / 2;
        vec2i cell = f2i(midp) - vec2i(midp.x == f2i(midp.x), midp.y == f2i(midp.y)) * (midp - origin_pos < 0);
        vec2i walls1 = cell + (p1 - origin_pos > 0);
        vec2 t1 = ((vec2)walls1 - p1) / (p1 - origin_pos);
        vec2i walls2 = cell + (p2 - origin_pos > 0);
        vec2 t2 = ((vec2)walls2 - p2) / (p2 - origin_pos);
        vec2 p_1 = p1 + (p1 - origin_pos) * t1.min();
        if(t1.x < t1.y) p_1.x = walls1.x;
        else p_1.y = walls1.y;
        vec2 p_2 = p2 + (p2 - origin_pos) * t2.min();
        if(t2.x < t2.y) p_2.x = walls2.x;
        else p_2.y = walls2.y;
        std::vector<vec2> polygon;
        polygon.push_back(p_2);
        if(abs(p2 - p_2) > DELTA) polygon.push_back(p2);
        if(abs(p1 - p_1) > DELTA) polygon.push_back(p1);
        polygon.push_back(p_1);
        if(cross(walls1 - p_1, origin_pos - walls1) >= 0 && cross(p_2 - walls1, origin_pos - walls1) >= 0
           && abs(walls1 - p_1) > DELTA && abs(p_2 - walls1) > DELTA)
            polygon.push_back(walls1);
        if(cross(walls2 - walls1, origin_pos - walls2) >= 0 && cross(p_2 - walls2, origin_pos - walls2) >= 0
           && abs(walls2 - walls1) > DELTA && abs(p_2 - walls2) > DELTA)
            polygon.push_back(walls2);
        return std::pair<vec2i, std::vector<vec2>>{cell, polygon};
    }

    std::vector<Room_info> split_image() {
        vec2i min_room_coords(0, 0);
        vec2i max_room_coords(0, 0);
        for(vec2 corner : std::vector<vec2>{{1, -1}, {1, 1}, {-1, 1}, {-1, -1}}) {
            vec2i corner_coords = rotate((vec2)image_size / 2 / room_size * corner, -angle) + origin_pos;
            min_room_coords = min(min_room_coords, f2i(corner_coords));
            max_room_coords = max(max_room_coords, -f2i(-corner_coords));
        }
        std::vector<vec2> polygon0 = {{0, 0}, {1, 0}, {1, 1}, {0, 1}};
        std::vector<Room_info> polygons;
        std::vector<Room_info> extruded_polygons;
        std::vector<Room_info> new_polygons(1, Room_info{0, origin_room, vec2(0, 0), polygon0});
        while(new_polygons.size()) {
            for(Room_info room_info : new_polygons) extruded_polygons.push_back(room_info);
            new_polygons.clear();
            for(Room_info room_info : extruded_polygons) {
                for(int i = 0; i < room_info.polygon.size(); i ++) {
                    vec2 p1 = room_info.polygon[i];
                    vec2 p2 = room_info.polygon[(i + 1) % room_info.polygon.size()];
                    vec2 v = (p1 + p2) / 2 - origin_pos;
                    if(cross(p1 - p2, v) < DELTA) continue;
                    int door;
                    if(std::abs(p1.x - p2.x) > std::abs(p1.y - p2.y)) door = v.y > 0 ? 2 : 0;
                    else door = v.x > 0 ? 1 : 3;
                    door = (door + 4 - room_info.rotaion) % 4;
                    if(room_info.room->connected_rooms[door] < 0) continue;
                    Room * room = &rooms[room_info.room->connected_rooms[door]];
                    std::pair<vec2i, std::vector<vec2>> extruded = extrude(p1, p2);
                    int rotation = (room_info.rotaion + 4 + room_info.room->relative_rotatation(door)) % 4;
                    if((min_room_coords <= extruded.first).all() && (extruded.first < max_room_coords).all())
                        new_polygons.push_back(Room_info{rotation, room, extruded.first, extruded.second});
                }
            }
            for(Room_info room_info : extruded_polygons) polygons.push_back(room_info);
            extruded_polygons.clear();
        }
        for(Room_info & room_info : polygons) {
            for(vec2 & point : room_info.polygon)
                point = rotate(point - (vec2)room_info.origin, -room_info.rotaion * PI / 2);
            room_info.origin = rotate((room_info.origin - origin_pos) * room_size, angle) + (vec2)image_size / 2;
        }
        return polygons;
    }
    
    void update_objects(std::vector<Room*> rooms) {
        for(Room * room : rooms)
            room->clear();
        for(Room * room : rooms)
            room->apply_objects();
    }

    void draw(sf::RenderWindow & window) {
        std::vector<Room_info> polygons = split_image();
        std::vector<Room*> rendered_rooms;
        for(Room_info ri : polygons) rendered_rooms.push_back(ri.room);
        update_objects(rendered_rooms);
        for(int i = 0; i < polygons.size(); i ++) {
            if(polygons[i].room->id < 0) continue;
            std::vector<vec2> polygon = polygons[i].polygon;
            sf::ConvexShape convex;
            convex.setPointCount(polygon.size());
            vec2 min_point(1., 1.);
            vec2 max_point(-1., -1.);
            for(int j = 0; j < polygon.size(); j ++) {
                convex.setPoint(j, polygon[j].sf());
                min_point = min(min_point, polygon[j]);
                max_point = max(max_point, polygon[j]);
            }
            max_point += (min_point + vec2(.0001, .0001) < 0);
            min_point += (min_point + vec2(.0001, .0001) < 0);
            convex.setTextureRect(sf::IntRect((min_point * room_size).sf_i(), ((max_point - min_point) * room_size).sf_i()));
            convex.setTexture(&polygons[i].room->texture.getTexture());
            convex.setPosition(polygons[i].origin.sf());
            convex.setRotation(angle * 180 / PI + 90 * polygons[i].rotaion);
            convex.setScale(room_size, room_size);
            window.draw(convex);
        }
    }

    Room & add_room(sf::Color color) {
        return Room::new_room(&rooms, color, room_size);
    }

    void move(vec2 shift, bool retry = true) {
        shift = -rotate(shift, -angle);
        // std::cout << shift << std::endl;
        vec2 p = origin_pos + shift;
        std::pair<int, Room*> new_origin = get_room(p);
        if(new_origin.second->id >= 0) {
            if(new_origin.second->id == 1 && new_origin.second->id != origin_room->id)
                std::cout << "You found the apple!!" << std::endl;
            origin_pos += shift;
            origin_pos -= f2i(origin_pos);
            origin_pos = vec2(.5, .5) + rotate(origin_pos - vec2(.5, .5), -new_origin.first * PI / 2);
            origin_room->remove_object(&human);
            origin_room = new_origin.second;
            origin_room->add_object(&human);
            angle += new_origin.first * PI / 2;
            vec2 human_pos = (origin_pos) * room_size;
            human.setPosition(human_pos.x, room_size - human_pos.y);
            human.setRotation(angle * 180 / PI);
        } else if(retry) {
            vec2 old_origin_pos = origin_pos;
            move(-rotate(vec2(p.x, std::min(std::max(p.y, DELTA), 1. - DELTA)) - origin_pos, angle), false);
            if(origin_pos == old_origin_pos)
                move(-rotate(vec2(std::min(std::max(p.x, DELTA), 1. - DELTA), p.y) - origin_pos, angle), false);
        }
    }

    void poop() {
        poops.push_back(sf::RectangleShape(sf::Vector2f(10, 10)));
        sf::RectangleShape & p = *(--poops.end());
        p.setOrigin(((vec2)p.getSize() / 2).sf());
        p.setFillColor(sf::Color(128, 64, 64));
        p.setOutlineThickness(2);
        p.setOutlineColor(sf::Color::Black);
        p.setPosition(human.getPosition());
        p.setRotation(human.getRotation());
        origin_room->add_object(&p);
        if(poops.size() > 40) {
            for(std::pair<const int, Room> & room_pair : rooms)
                room_pair.second.remove_object(&(*poops.begin()));
            poops.erase(poops.begin());
        }
    }

    void mark() {
        marks.push_back(sf::CircleShape(15.));
        sf::CircleShape & m = *(--marks.end());
        m.setOrigin(m.getRadius(), m.getRadius());
        m.setFillColor(sf::Color::Red);
        m.setOutlineThickness(3);
        m.setOutlineColor(sf::Color::Black);
        m.setPosition(human.getPosition());
        m.setRotation(human.getRotation());
        origin_room->add_object(&m);
    }
};

int main(void) {
    srand(1);

    sf::Texture apple_texture;
    apple_texture.loadFromFile("apple.png");
    sf::RectangleShape apple(sf::Vector2f(60, 60));
    apple.setOrigin(30, 30);
    apple.setRotation(20);
    apple.setTexture(&apple_texture);
    apple.setScale(1, -1);
    apple.setPosition(40, 40);

    sf::Texture pacman_texture;
    pacman_texture.loadFromFile("pacman.png");
    sf::RectangleShape pacman(sf::Vector2f(20, 20));
    pacman.setOrigin(10, 10);
    pacman.setTexture(&pacman_texture);
    pacman.setScale(1, -1);
    Backrooms br(pacman, 80);

    br.add_random(200);

    sf::RectangleShape rect(sf::Vector2f(50, 50));
    rect.setOrigin(rect.getSize().x / 2, rect.getSize().y / 2);
    rect.setFillColor(sf::Color(100, 130, 150));
    rect.setOutlineColor(sf::Color::Black);
    rect.setOutlineThickness(3);
    rect.setPosition(br.room_size / 2, br.room_size / 2);
    rect.setRotation(10);
    // room1.add_object(&rect);
    br.origin_room->add_object(&rect);
    br.rooms[1].add_object(&apple);

    // br.update_objects();
    sf::RenderWindow window(sf::VideoMode(1080, 720), "Find apple");
    std::chrono::time_point<std::chrono::system_clock> t = std::chrono::system_clock::now();
    double no_pooping_dist = 0.;
    while(window.isOpen()) {
        sf::Event event;
        while(window.pollEvent(event)) {
            switch(event.type) {
                case sf::Event::Closed:
                    window.close();
                    break;
                case sf::Event::Resized:
                    br.image_size.x = event.size.width;
                    br.image_size.y = event.size.height;
                    window.setView(sf::View(sf::FloatRect(0, 0, event.size.width, event.size.height)));
                    break;
                case sf::Event::KeyPressed:
                    if(event.key.code == sf::Keyboard::M) {
                        std::cout << "Mark" << std::endl;
                        br.mark();
                    }
                    break;
            }
        }
        std::chrono::time_point<std::chrono::system_clock> t2 = std::chrono::system_clock::now();
        double dt = std::chrono::duration<double>(t - t2).count();
        t = t2;
        vec2 shift(0., 0.);
        double angle_shift = 0.;
        if(window.hasFocus()) {
            if(sf::Keyboard::isKeyPressed(sf::Keyboard::W)) shift += vec2(0., -1.) * dt;
            if(sf::Keyboard::isKeyPressed(sf::Keyboard::Up)) shift += vec2(0., -1.) * dt;
            if(sf::Keyboard::isKeyPressed(sf::Keyboard::A)) shift += vec2(-1., 0.) * dt;
            if(sf::Keyboard::isKeyPressed(sf::Keyboard::S)) shift += vec2(0., 1.) * dt;
            if(sf::Keyboard::isKeyPressed(sf::Keyboard::Down)) shift += vec2(0., 1.) * dt;
            if(sf::Keyboard::isKeyPressed(sf::Keyboard::D)) shift += vec2(1., 0.) * dt;
            if(sf::Keyboard::isKeyPressed(sf::Keyboard::Left)) angle_shift -= dt;
            if(sf::Keyboard::isKeyPressed(sf::Keyboard::Q)) angle_shift -= dt;
            if(sf::Keyboard::isKeyPressed(sf::Keyboard::Right)) angle_shift += dt;
            if(sf::Keyboard::isKeyPressed(sf::Keyboard::E)) angle_shift += dt;
            if(sf::Keyboard::isKeyPressed(sf::Keyboard::RShift)) { shift *= 2; angle_shift *= 2; }
            if(sf::Keyboard::isKeyPressed(sf::Keyboard::LShift)) { shift *= 2; angle_shift *= 2; }
        }
        no_pooping_dist += abs(shift);
        if(no_pooping_dist >= 0.8) {
            br.poop();
            no_pooping_dist = 0.;
        }
        br.angle += angle_shift;
        br.move(shift);
        window.clear();
        br.draw(window);
        window.display();
    }
    return 0;
}
